package org.xi.dsaa.collection;

/**
 * AVL树 Adelson-Velsky 和 Landis
 * AVL树本质上还是一棵二叉搜索树，它的特点是：
 * 1.本身首先是一棵二叉搜索树。
 * 2.带有平衡条件：每个结点的左右子树的高度之差的绝对值（平衡因子）最多为1。
 * <p>
 * 在计算机科学中，AVL树是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别为1，所以它也被称为高度平衡树。
 * 增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。AVL树得名于它的发明者G. M. Adelson-Velsky和E. M. Landis
 *
 * @param <E> 元素类型
 */
public class AvlTree<E extends Comparable<E>> {

    private Node<E> root;

    public boolean isEmpty() {
        return root == null;
    }

    public boolean exists(E value) {
        Node<E> node = root;
        while (node != null) {
            int compareResult = node.item.compareTo(value);
            if (compareResult > 0) {
                node = node.left;
            } else if (compareResult < 0) {
                node = node.right;
            } else {
                return true;
            }
        }
        return false;
    }

    public void add(E item) {
        root = add(item, root);
    }

    private Node<E> add(E item, Node<E> node) {
        if (node == null) {
            return new Node<>(item);
        }
        int compareResult = item.compareTo(node.item);
        if (compareResult == 0) return node;

        if (compareResult < 0) {
            node.left = add(item, node.left);
            if (getHeight(node.left) - getHeight(node.right) == 2) {
                node = item.compareTo(node.left.item) < 0 ? singleRotateWithLeft(node) : doubleRotateWithLeft(node);
            }
        } else {
            node.right = add(item, node.right);
            if (getHeight(node.right) - getHeight(node.left) == 2) {
                node = item.compareTo(node.right.item) > 0 ? singleRotateWithRight(node) : doubleRotateWithRight(node);
            }
        }
        node.height = Math.max(getHeight(node.left), getHeight(node.right)) + 1;
        return node;
    }

    private int getHeight(Node<E> node) {
        return node == null ? 0 : node.height;
    }

    private Node<E> singleRotateWithLeft(Node<E> node) {
        Node<E> tmpNode = node.left;
        node.left = tmpNode.right;
        tmpNode.right = node;

        node.height = Math.max(getHeight(node.left), getHeight(node.right)) + 1;
        tmpNode.height = Math.max(getHeight(tmpNode.left), node.height) + 1;
        return tmpNode;
    }

    private Node<E> doubleRotateWithLeft(Node<E> node) {
        node.left = singleRotateWithRight(node.left);
        return singleRotateWithLeft(node);
    }

    private Node<E> singleRotateWithRight(Node<E> node) {
        Node<E> tmpNode = node.right;
        node.right = tmpNode.left;
        tmpNode.left = node;

        node.height = Math.max(getHeight(node.left), getHeight(node.right)) + 1;
        tmpNode.height = Math.max(getHeight(tmpNode.right), node.height) + 1;
        return tmpNode;
    }

    private Node<E> doubleRotateWithRight(Node<E> node) {
        node.right = singleRotateWithLeft(node.right);
        return singleRotateWithRight(node);
    }

    public void addAll(E... items) {
        for (E item : items) {
            add(item);
        }
    }

    public void addAll(Iterable<E> items) {
        for (E item : items) {
            add(item);
        }
    }

    public void remove(E item) {
        root = remove(item, root);
    }

    public Node<E> remove(E item, Node<E> node) {
        if (node == null) return null;
        int compareResult = item.compareTo(node.item);
        if (compareResult < 0) {
            node.left = remove(item, node.left);
            // 只有删除到叶子节点才会出现高度相差为2的情况，此时，左子树为null
            if (getHeight(node.right) - getHeight(node.left) == 2) {
                node = singleRotateWithRight(node);
            }
        } else if (compareResult > 0) {
            node.right = remove(item, node.right);
            // 只有删除到叶子节点才会出现高度相差为2的情况，此时，右子树为null
            if (getHeight(node.left) - getHeight(node.right) == 2) {
                node = singleRotateWithLeft(node);
            }
        } else if (node.left != null && node.right != null) {
            if (node.left.height > node.right.height) {
                Node<E> maxNode = getMaxNode(node.left);
                node.item = maxNode.item;
                node.left = remove(maxNode.item, node.left);
            } else {
                Node<E> minNode = getMinNode(node.right);
                node.item = minNode.item;
                node.right = remove(minNode.item, node.right);
            }
        } else {
            // 仅有此时会出现，左子树和右子树的高度相差为2的情况
            node = node.left != null ? node.left : node.right;
        }
        if (node != null) {
            node.height = Math.max(getHeight(node.left), getHeight(node.right)) + 1;
        }
        return node;
    }

    private Node<E> getMinNode(final Node<E> node) {
        Node<E> currentNode = node;
        if (currentNode == null) {
            return null;
        }
        while (currentNode.left != null) {
            currentNode = currentNode.left;
        }
        return currentNode;
    }

    private Node<E> getMaxNode(final Node<E> node) {
        Node<E> currentNode = node;
        if (currentNode == null) {
            return null;
        }
        while (currentNode.right != null) {
            currentNode = currentNode.right;
        }
        return currentNode;
    }

    public void printTree() {
        printTree(root);
    }

    private void printTree(Node<E> node) {
        if (node.left != null) {
            printTree(node.left);
        }
        System.out.println(node.item);
        if (node.right != null) {
            printTree(node.right);
        }
    }

    public static class Node<E extends Comparable<E>> {
        private E item;
        private Node<E> left;
        private Node<E> right;
        private int height;

        public Node(E item) {
            this(item, null, null, 1);
        }

        public Node(E item, Node<E> left, Node<E> right, int height) {
            this.item = item;
            this.left = left;
            this.right = right;
            this.height = height;
        }
    }

    public static void main(String[] args) {
        AvlTree<Integer> tree = new AvlTree<>();
        tree.addAll(32, 24, 6, 3, 4, 19, 40, 9, 8, 3, 16, 10, 23, 31, 67, 18);
        tree.printTree();

        System.out.println();
        System.out.println();
        tree.remove(24);
        tree.printTree();

        System.out.println();
        System.out.println();
        tree.remove(9);
        tree.printTree();
    }
}
